The present invention relates to techniques for performing arithmetic operations on data.
Wilson, U.S. Pat. No. 5,129,092 ("Wilson '092"), describes techniques for processing data matrices such as images and spatially related data using neighborhood processing units. As shown and described in relation to FIGS. 1 and 2, the processing units form an array with several groups of eight processing units. Each processing unit's connections to its adjacent processing units to the immediate left and right in the array include a carry in line to its left and a carry out line to the right.
Wilson '092 describes arithmetic operations beginning at col. 12 line 40. In bit serial arithmetic, a carry signal from a carry flip-flop is passed to multiplexers, one of which acts as a truth table for a carry propagate value, which is stored in flip-flops, provided to an output selector, and can be read back to memory. In parallel arithmetic, a carry input from a processing unit to the immediate left is obtained and a carry output propagates to a processing unit to the immediate right. When performing parallel arithmetic operations, care must be used in writing algorithms in order to avoid overflow, so that carry signals will not accidentally propagate from one data word to the next, since many data words are on the same line of bits.
Mahoney, EP-A 460 970, describes techniques for operating on a body of data such as data defining an image. FIG. 7 shows a Connection Machine system that performs image processing by simulating a binary image jungle (BIJ). A front end processor can make calls to cause processing units in the Connection Machine to perform arithmetic and logical operations. FIG. 8 illustrates a part of an array of processing units in a Connection Machine, with a processing unit storing a pixel value of an image at a lowest level of a BIJ and receiving a pixel value from another processing unit at the next higher level of the BIJ. As described at page 20 lines 15-28 in relation to FIG. 10, each processing unit operates on the results from the next lower level of its first and second children. FIGS. 13 and 14 each show a sequence of data item arrays in which sums of pixel values are obtained. As described in relation to FIG. 18, each processing unit's local memory can contain a respective pixel's value.